package pro11_20.pro15;

import utils.binarytree.BinaryTree;
import utils.binarytree.TreeNode;

import java.util.LinkedList;

/**
 * @author yaohuaiying
 * @create 2018-02-09 14:41
 * 第15题（树）：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ /
6 10
// //
5 7 9 11
输出：
8
/ /
10 6
// //
11 9 7 5
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};


思路：
    其实就是打印的时候反向打印吧
    根据这种输入生树？？？？需要吗 ？
    如果单纯的做题的话 其实吧每一层的输入反向打印一下就行了
    好吧 我们还是来做一下 树的镜像把 老实一点。。。。循环和递归
    首先要思考这种输入怎么变成树（字符的切割） 算了先不想了
    先去把层级打印写出来  。。。。好像要先写个队列。。。。emmm  为了后面的方便！
    然后emmm..好像翻一下就行了
    递归的....思考一下
 **/
public class Main {
    public static void main(String[] args){
        BinaryTree tree = BinaryTree.createBinaryTree(10);
        tree.treePrint(4);
        System.out.println("正常的层级打印");
        tree.BFSPrint();
        System.out.println("镜像的层级打印");
        testPrint(tree);
    }

    private static void testPrint(BinaryTree tree){
        LinkedList<TreeNode> BFSQueue = new LinkedList<>();
        if(tree.getRoot() != null) {
            TreeNode currentNode = tree.getRoot();
            BFSQueue.addLast(tree.getRoot());
            while (!BFSQueue.isEmpty()) {
                //父出 子进
                currentNode =BFSQueue.removeFirst();
                System.out.print(currentNode.getData() + "  ");
                if(currentNode.getRight() != null){
                    BFSQueue.addLast(currentNode.getRight());
                }
                if(currentNode.getLeft() != null){
                    BFSQueue.addLast(currentNode.getLeft());
                }
            }
        }
    }

}
